class Solution {
public:
    int longestSubsequence(string s, int k) {
        
        int ret=0;
        int cur=0;
        int n=s.size();
        vector<int> bac(n+1);
        for(int i=n-1;i>=0;--i){

            bac[i]=bac[i+1]+(s[i]=='1'?1:0);
            if(s[i]=='0'){

                ret++;
            }
            else{
                
                if(n-1-i>30){
                    continue;
                }
                int t=cur|1<<(n-1-i);
                if(t<=k){

                    ret++;
                    cur=t;
                }
            }
        }

        return ret;
    }
};
